import util.ListNode;

/**
 * Created by loso on 2017/3/17.
 */
public class _234_PalindromeLinkedList {

    public static void main(String[] args) {
        ListNode a = new ListNode(0);
        a.next = new ListNode(0);

        _234_PalindromeLinkedList b = new _234_PalindromeLinkedList();
        System.out.println(b.isPalindrome(a));
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null){
            return true;
        }
        ListNode walker = head;
        ListNode runner = head;
        ListNode temp;
        ListNode nextwalker = head.next;
        while (runner.next != null && runner.next.next != null){
            runner = runner.next.next;
            temp = walker;
            walker = nextwalker;
            nextwalker = walker.next;
            walker.next = temp;
        }

        if (runner.next == null){
            walker = walker.next;
        }
        head.next = null;
            while (walker != null && nextwalker != null){
                if (walker.val==nextwalker.val){
                    nextwalker = nextwalker.next;
                    walker = walker.next;
                }else{
                    return false;
                }
            }
            if (walker!=nextwalker){
                return false;
            }

        return true;
    }
}
